#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    vector<int> sortArray(vector<int> &nums)
    {
        vector<int>help(nums.size());
        mergesort(nums,help,0,nums.size()-1);
        return nums;
    }
    //left:0 right=9
    void mergesort(vector<int>&nums,vector<int>&help,int left,int right)
    {
        if(left>=right) return;
        int mid=(right-left)/2+left;
        mergesort(nums,help,left,mid);
        mergesort(nums,help,mid+1,right);
        int begin1=left;
        int end1=mid;
        int begin2=mid+1;
        int end2=right;
        int index=left;
        while(begin1<=end1&&begin2<=end2)
        {
            if(nums[begin1]<=nums[begin2])
            {
                help[index++]=nums[begin1++];
            }
            else
            {
                help[index++]=nums[begin2++];
            }
        }
        while(begin1<=end1) help[index++]=nums[begin1++];
        while(begin2<=end2) help[index++]=nums[begin2++];
        for(int i=left;i<=right;i++)
        {
            nums[i]=help[i];
        }
    }
};